Usenet 1993 July/InfoMagic USENET CD-ROM July 1993.ISO/sources/misc/volume5/malloc.uport

Internet Message Format | 1989-02-03 | 24.6 KB

Path: xanth!nic.MR.NET!hal!ncoast!allbery
From: [e-mail] (Michael Grenier)
Newsgroups: comp.sources.misc
Subject: v05i048: m286 - Fast malloc for Microport
Message-ID: <[e-mail]>
Date: 15 Nov 88 00:24:36 GMT
Sender: [e-mail]
Reply-To: [e-mail] (Michael Grenier)
Lines: 908
Approved: [e-mail]

Posting-number: Volume 5, Issue 48
Submitted-by: "Michael Grenier" <[e-mail]>
Archive-name: malloc.uport

Brandon,
   Here is a fast malloc package for Microport V/AT which performs
at least 10 times faster than malloc(3C). As an example, on this
Microport Version 2.3 system, it does the simple memory allocation
test about 150 times faster than malloc(3X). Hopefully, someone will
send me the bechmarks comparing it to version 2.4.

This package makes heavy use of the Intel 80286 architecture and
is thus not very portable. XENIX people may be able to use it though
their malloc may perform reasonably well.

    -Mike Grenier
    [e-mail]
    rutgers!bungia!cimcor!mike
    uunet!rosevax!cimcor!mike

#! /bin/sh
# This is a shell archive, meaning:
# 1. Remove everything above the #! /bin/sh line.
# 2. Save the resulting text in a file.
# 3. Execute the file with /bin/sh (not csh) to create:
#    README
#    Makefile
#    malloc.c
#    m286.3x
#    t.c
#    tcheck.c
# This archive created: Wed Nov  9 07:44:21 1988
export PATH; PATH=/bin:/usr/bin:$PATH
echo shar: "extracting 'README'" '(1546 characters)'
if test -f 'README'
then
    echo shar: "will not over-write existing file 'README'"
else
sed 's/^    X//' << \SHAR_EOF > 'README'
    X    m286 - fast malloc for Microport 286
    X    Michael Grenier   11/8/88
    X
    XA couple quick notes on m286 :
    X    - Binaries of this package were sent out via comp.unix.microport some
    X    months ago. It has since been modified slightly to include
    X    limited checking for bad pointers in free().
    X
    X    - m286 seems to perform about 10 to 50 times faster than malloc(3C)
    X    under Microport version 2.3 and earlier. I haven't had a chance to
    X    benchmark it against v2.4 using malloc(3X)...hopefully someone will
    X    send me the tests results.
    X
    X    - This package makes heavy use of the Intel 80286 processor
    X    specifics. It might be portable to XENIX provided the brk()
    X    system call always returns a new segment as it does under
    X    Microport. Of course, malloc under XENIX may already perform
    X    reasonably well.
    X
    X    - The algorithm is based on the boundary tag system presented
    X    in the book Fundamentals of Data Structures written by
    X    Sahni and Horowitz.
    X
    X    -Please send me bug reports!! [e-mail]
    X
    X
    XHere are the test results from my 8 Mhz 1 wait state machine. The
    Xreal time is significant as these test were run on an otherwise quiet
    Xmachine. The big time difference seems to be due to the OS swapping
    Xprocesses for every brk() system call.
    X
    XBeginning test of standard malloc(3C) for allocating 400K bytes
    Xreal     2:06.1
    Xuser       37.6
    Xsys        14.3
    X
    XBeginning test of standard malloc(3X) for allocating 400K bytes
    Xreal    21:39.6
    Xuser        1.0
    Xsys         3.0
    X
    XBeginning test of standard m286(3X) for allocating 400K bytes
    Xreal        8.4
    Xuser        1.2
    Xsys         1.6
SHAR_EOF
if test 1546 -ne "`wc -c < 'README'`"
then
    echo shar: "error transmitting 'README'" '(should have been 1546 characters)'
fi
fi
echo shar: "extracting 'Makefile'" '(1446 characters)'
if test -f 'Makefile'
then
    echo shar: "will not over-write existing file 'Makefile'"
else
sed 's/^    X//' << \SHAR_EOF > 'Makefile'
    X# Simple Makefile for fast malloc library
    X#
    X# For Microport do:
    X#       make lib
    X#      su root
    X#    make install
    X#
    X# To try out the test programs do :
    X#
    X#    make tests
    X#
    X# Tests results are placed in the file 't-results'
    X#
    XCFLAGS= -Ml -O
    XCC=cc
    XLIBDIR=/usr/lib/large
    Xlib : malloc.o
    X    ar rv libm286.a malloc.o
    Xinstall : libm286.a
    X    mv libm286.a $(LIBDIR)
    X    chmod 644 $(LIBDIR)/libm286.a
    X    chgrp bin $(LIBDIR)/libm286.a
    X    chown bin $(LIBDIR)/libm286.a
    Xmalloc.o : /usr/include/malloc.h
    X    $(CC) $(CFLAGS) -c malloc.c
    X
    Xtests : t-m286 tc-m286 $(LIBDIR)/libm286.a
    X    @echo 'Beginning tests .... This will take awhile'
    X    @echo 'Beginning test of standard malloc(3C) for allocating 400K bytes'
    X    @echo 'Beginning test of standard malloc(3C) for allocating 400K bytes' >t-results
    X    time t-malloc 400 2>>t-results
    X    @echo 'Beginning test of standard malloc(3X) for allocating 400K bytes' >>t-results
    X    @echo 'Beginning test of standard malloc(3X) for allocating 400K bytes'
    X    -time t-malloc3x 400 2>>t-results
    X    @echo 'Beginning test of standard m286(3X) for allocating 400K bytes' >>t-results
    X    @echo 'Beginning test of standard m286(3X) for allocating 400K bytes'
    X    time t-m286 400 2>>t-results
    X
    Xt-m286 : t.o
    X    $(CC) $(CFLAGS) -o t-m286 t.o -lm286
    X    $(CC) $(CFLAGS) -o t-malloc t.o
    X    $(CC) $(CFLAGS) -o t-malloc3x t.o -lmalloc
    X
    Xtc-m286 : tcheck.o
    X    $(CC) $(CFLAGS) -o tc-m286 tcheck.o -lm286
    X    $(CC) $(CFLAGS) -o tc-malloc tcheck.o
    X    $(CC) $(CFLAGS) -o tc-malloc3x tcheck.o -lmalloc
    X
    X
SHAR_EOF
if test 1446 -ne "`wc -c < 'Makefile'`"
then
    echo shar: "error transmitting 'Makefile'" '(should have been 1446 characters)'
fi
fi
echo shar: "extracting 'malloc.c'" '(12693 characters)'
if test -f 'malloc.c'
then
    echo shar: "will not over-write existing file 'malloc.c'"
else
sed 's/^    X//' << \SHAR_EOF > 'malloc.c'
    X
    X/*
    X        Fast Malloc for Microport 286
    X        Copyright (C) April 1988
    X        Michael Grenier
    X
    XPermission to redistribute for non-profit use is hereby granted.
    XPlease send bug fixes to [e-mail]
    X
    X*/
    X#include <stdio.h>
    X#include <memory.h>
    X
    X/*  TUNABLE PARAMETERS */
    X
    X
    X#define EPSILON        10  /* Blocks smaller than this number of words are not
    X                retained */
    X
    X
    X/* DO NOT CHANGE! */
    X#define ALLOCATED    1
    X#define AVAILABLE    0
    X#define MAX_BLOCK_SIZE 32744          /* maximum size block we can allocate -
    X                        32768 - 4 * HEADER_SIZE  words */
    X#define LLINK(x)    (page[x])    /* pointer to previous block in page */
    X#define TAG(x)        (page[x+1])  /* set to 1 if allocated */
    X#define SIZE(x)        (page[x+2])  /* Number of words in this block not counting header */
    X#define RLINK(x)    (page[x+3])  /* pointer to next block */
    X#define ETAG(x)        (page[x+SIZE(x)+4])  /* set to 1 if allocated */
    X#define ULINK(x)    (page[x+SIZE(x)+5])  /* pointer to beginning of this block */
    X#define AV(indx)    (av_list[indx])      /* pointer to block on free list with this page */
    X
    Xstatic char *xxcopyright="\n\n\nCopyright 1988 by Michael Grenier, all rights reserved\n\n";
    X
    Xchar *sbrk();   /* needed Unix System calls */
    Xint    brk();
    X
    Xstatic unsigned av_list[62],   /* offset pointer to a free block with each page */
    X     m_curindx=0,    /* Current page to allocate from */
    X     free_indx=1;    /* Page to begin searching for a block in */
    X
    Xstatic int xxfunny[4]={23,56,12,23}; /* used to uniquely identify this binary should
    X                someone steal the start distributing binaries
    X                and delete the copyright */
    X
    X#define HEADER_SIZE    6 /* words wasted per block */
    X#define ALLOCATE_OFFSET 4 /* Offset in block where user process pointer points */
    X
    Xstatic long m_endds, m_first_endds; /* address of current and initial brk() value */
    X
    X
    X/* Get starting address of this segment given segment number
    X   starting with one as the first segment allocated
    X*/
    Xunsigned int *getpage(indx)
    Xunsigned indx;
    X{
    X    return (unsigned int *) ((m_first_endds + ((unsigned long)indx - 1L)
    X         * 0x00080000L) & 0xFFFF0000L); /* adjust selector */
    X}
    X
    X
    X
    X/* can't use stock memcpy, memset as they don't handle a size
    X    greater than 32K bytes */
    X
    Xvoid u_memset(ptr, value, size) /* in words */
    Xunsigned int *ptr, value, size;
    X{
    X    while (!size)
    X    {
    X        (*(ptr++)) = value;
    X        size--;
    X    }
    X}
    X
    Xvoid u_memcpy(ptr1, ptr2, size) /* in words, should be written in asssembler ti use block moves */
    Xunsigned int *ptr1, *ptr2, size;
    X{
    X    while (!size)
    X    {
    X        (*(ptr1++)) = *(ptr2++);
    X        size--;
    X    }
    X}
    X
    X
    X/*
    X    New_page() - allocate a new segment from Unix
    X    This routine allocates a full 64K segment to be supplied to malloc
    X    to be split up as appropiate
    X*/
    Xvoid new_page()
    X{
    X    unsigned temp, *page;
    X
    X    if (m_curindx==0) /* First time so initialize a segment */
    X    {
    X        m_first_endds = (long) sbrk(0);  /* returns next segment value */
    X        m_endds = m_first_endds + 65535L;
    X    }
    X    else
    X        m_endds += 0x00080000L; /* add one to 80286 selector */
    X
    X    brk((char *) m_endds);    /* allocates the new page (segment) */
    X
    X    /* Now set up free list in segment. Allocate and tag busy two zero
    X       length blocks on each end of page to simplify and speed up
    X       allocation algorithm - see Sahni's notes. Also allocate a
    X       zero length free segment and set AV to point to it.
    X    */
    X
    X    m_curindx++;  /* Update number of pages allocated */
    X    page = getpage (m_curindx); /* set up to use macros */
    X
    X    TAG(0)    = ALLOCATED;  /* allocate zero length block at start of page */
    X    SIZE(0)    = 0;
    X    ETAG(0)    = ALLOCATED;
    X    ULINK(0)= 0;
    X
    X
    X
    X    temp = 32768 - HEADER_SIZE;/* point to last possible block in page
    X                      and allocate it also */
    X
    X    TAG(temp)   = ALLOCATED;
    X    SIZE(temp)  = 0;
    X    ETAG(temp)  = ALLOCATED;
    X    ULINK(temp) = temp;
    X
    X
    X
    X    temp = HEADER_SIZE; /* Now allocate a zero length free block that
    X                   will never get allocated (because of its size) */
    X
    X    TAG(temp)   = AVAILABLE;
    X    SIZE(temp)  = 0;
    X    LLINK(temp) = temp + HEADER_SIZE; /* point to next block (yet to be
    X                         created) which will be the actual
    X                         free block */
    X    ETAG(temp)  = AVAILABLE;
    X    ULINK(temp) = temp;
    X    RLINK(temp) = temp + HEADER_SIZE;
    X    av_list[m_curindx] = temp;      /* point to first free block */
    X
    X
    X    temp += HEADER_SIZE;  /* Finally, allocate the actual free block */
    X    TAG(temp) = AVAILABLE;  /* mark as free */
    X    SIZE(temp) = MAX_BLOCK_SIZE;
    X    LLINK(temp) = HEADER_SIZE; /* point to previous free block */
    X    RLINK(temp) = HEADER_SIZE;
    X    ETAG(temp)  = AVAILABLE;
    X    ULINK(temp) = temp;
    X}
    X
    Xunsigned int get_offset(ptr)
    Xunsigned int *ptr; /* not char * because we want pointer math in words, not bytes */
    X{
    X    unsigned int temp = (((unsigned) ptr >>1) - ALLOCATE_OFFSET);
    X    return temp;
    X}
    X
    X
    Xvoid free_from_page(p, seqindx)
    Xunsigned int p, seqindx;
    X{
    X    unsigned int n, q, r, *page;
    X
    X    /* point to true beginning of block */
    X
    X    page = getpage(seqindx);
    X
    X    if ((TAG(p) != ALLOCATED) || (ETAG(p) != ALLOCATED))
    X    {
    X        fprintf(stderr,"\n\rAttempt to free a pointer which was not allocated\n");
    X        fprintf(stderr,"or had its control block information overwritten!\n");
    X        abort();
    X    }
    X
    X    n = SIZE(p);
    X
    X    if (((p==12) || (page[p-2]==ALLOCATED))
    X       && (TAG(p+n+HEADER_SIZE)==ALLOCATED))
    X    /* free this block but do not join with neighbors */
    X    {
    X        TAG(p)        = AVAILABLE;
    X        ETAG(p)            = AVAILABLE;
    X        ULINK(p)    = p;
    X        LLINK(p)    = AV(seqindx);
    X        RLINK(p)    = RLINK(AV(seqindx));
    X/*        LLINK(RLINK(p)    = p;        Can't seem to nest macros */
    X        page [ RLINK(p) ] = p;
    X        RLINK(AV(seqindx))    = p;
    X    }
    X    else if ((p!=12) &&    /* Never join with first empty block as AV must point to something */
    X        (page[p-2]==AVAILABLE) &&
    X        ((TAG(p+n+HEADER_SIZE))==ALLOCATED))
    X    /* join with left block */
    X    {
    X        q = page[p-1]; /* start of left block */
    X        SIZE(q) = SIZE(q) + n + HEADER_SIZE;
    X        ULINK(p) = q;
    X        ETAG(p)  = AVAILABLE;
    X        AV(seqindx) = q;     /* always leave AV pointing to possible full block */
    X    }
    X    else if (((p==12) || (page[p-2]==ALLOCATED)) &&
    X        ((TAG(p+n+HEADER_SIZE))==AVAILABLE))
    X    /* join with right block */
    X    {
    X        q = p + n + HEADER_SIZE; /* start of next block */
    X        page[ page[q] + 3] = p;  /* RLINK(LLINK(q))=p  stupid macros...*/
    X        page[page[q+3]]=p;   /*LLINK(RLINK(q)) = p; */
    X        LLINK(p) = LLINK(q);
    X        RLINK(p) = RLINK(q);
    X        SIZE(p) = n + HEADER_SIZE + SIZE(q);
    X        ULINK(p) = p;
    X        TAG(p) = AVAILABLE;
    X        AV(seqindx)=p; /* Can't have free list pointer pointing to
    X                    garbage! */
    X    }
    X    else
    X    {
    X        /* join with both sides */
    X        q = p + n + HEADER_SIZE; /* start of next block */
    X        r = page[p - 1];      /* start of previous block */
    X        RLINK(LLINK(q))=RLINK(q);
    X        LLINK(RLINK(q))=LLINK(q);
    X        SIZE(r)=SIZE(r) + (n + HEADER_SIZE) + SIZE(q) + HEADER_SIZE;
    X        ULINK(r)=r;
    X        AV(seqindx)=r; /* don't point to garbage */
    X    }
    X}
    X
    X
    X
    Xunsigned int *allocate_from_page(n, seqindx)
    Xunsigned int n, seqindx;
    X{
    X    unsigned int p, diff, *page;
    X    page = getpage(seqindx);
    X    p = AV(seqindx); /* point to first free block */
    X    do
    X    {    /* search for a free block, first fit */
    X        if (SIZE(p) >= n)  /* allocate it */
    X        {
    X            diff=SIZE(p)-n;
    X            if (diff < EPSILON) /* allocate whole block */
    X            {
    X                RLINK(LLINK(p)) = RLINK(p);
    X                LLINK(RLINK(p)) = LLINK(p);
    X                TAG(p)  = ALLOCATED;
    X                ETAG(p) = ALLOCATED;
    X                AV(seqindx) = LLINK(p);
    X                return(page + p + ALLOCATE_OFFSET);
    X            }
    X            else
    X            {    /* free lower portion of block */
    X                SIZE(p)  = diff - HEADER_SIZE; /* remaining free portion */
    X                ULINK(p) = p;
    X                ETAG(p)  = AVAILABLE;
    X                AV(seqindx) = p;
    X
    X                /* allocate the rest of block */
    X                p += SIZE(p) + HEADER_SIZE; /* point to start of block */
    X                SIZE(p) = n;
    X                TAG(p)  = ALLOCATED;
    X                ETAG(p) = ALLOCATED;
    X                ULINK(p) = p;
    X                return (page + p + ALLOCATE_OFFSET);
    X            }
    X        }
    X        p = RLINK(p); /* point to next free block */
    X    } while (p != AV(seqindx));
    X    return ((unsigned int *) 0);
    X}
    X
    X
    Xvoid return_free_pages()
    X{
    X    unsigned i, *page; /* leave one page allocated because this
    X            #*#*!& UNIX won't give you the intial brk value */
    X    while ((m_curindx>1) && (page=getpage(m_curindx),
    X            SIZE(AV(m_curindx)) == MAX_BLOCK_SIZE))
    X    {
    X        m_curindx--;
    X        m_endds -= 0x00080000L; /* subtract one from selector */
    X    };
    X    brk( (char *) m_endds);
    X}
    X
    X
    Xchar *malloc(size)
    Xunsigned size;
    X{
    X    char *dummy;
    X    int indx;
    X
    X    if (m_curindx==0)
    X        if (!new_page()) return((char *) 0); /* no more memory */
    X
    X    /* calculate page address */
    X
    X    indx=free_indx;
    X    do
    X    {
    X        if ((dummy = (char *) allocate_from_page((size+1)>>1, indx))
    X            !=NULL)
    X        {
    X            free_indx=indx; /* to speed up allocating for next malloc */
    X            return ((char *) dummy);
    X        }
    X        indx++;
    X        if (indx>m_curindx) indx=1;
    X    } while (indx != free_indx);
    X
    X/*  -- if we haven't returned yet, call brk for more memory and try again */
    X
    X    if (!new_page()) return((char *) 0);
    X    return((char *) allocate_from_page((size+1)>>1, m_curindx));
    X
    X}
    X
    X
    Xchar *calloc(nelem, elsize)
    Xunsigned nelem, elsize;
    X{
    X    char *dum;
    X    register unsigned size;
    X    size = nelem*elsize; /* in bytes, assume compiler word aligns structures */
    X    if ((dum=malloc(size)) != NULL)   /* zero out the block */
    X        u_memset( (int *) dum, 0, size>>1); /* set size words to 0 */
    X    return dum;
    X}
    X
    X
    Xvoid free(ptr)
    Xchar *ptr;
    X{
    X    unsigned int indx;
    X    long temp;
    X
    X    temp = (long) ptr - m_first_endds;
    X    indx = (temp >>19) + 1;        /* get selector for pointer */
    X    free_from_page(get_offset((unsigned int *)ptr), indx);
    X    return_free_pages();
    X}
    X
    X
    X
    Xchar *realloc( ptr, size)
    Xchar *ptr;
    Xunsigned size;
    X{
    X    unsigned int seqindx, *page, rb, p, diff;
    X    long temp;
    X    char * ptrnew;
    X
    X    if (size==0)
    X    {
    X        free(ptr);
    X        return (char *) NULL;
    X    }
    X
    X    temp = (long) ptr - m_first_endds;
    X    seqindx = (temp >>19) + 1;        /* get selector for pointer */
    X
    X    page = getpage(seqindx);
    X    p = get_offset((unsigned int *) ptr);
    X    size = (size + 1) >>1;                /* bytes to words, round up */
    X    diff =  SIZE(p) - size;     /* in words */
    X    if (size <= SIZE(p)) /* words, reduce space */
    X    {
    X        unsigned int rbnew;
    X
    X        if (diff<HEADER_SIZE)
    X            return ptr;    /* if can't create a new free block then */
    X                    /* waste the few bytes */
    X
    X        SIZE(p) -= diff;        /* modify this block */
    X        ULINK(p) =p;
    X        ETAG(p)  = ALLOCATED;
    X
    X        rbnew = p + HEADER_SIZE + SIZE(p); /* build new right block */
    X        TAG(rbnew) = ALLOCATED;
    X        SIZE(rbnew) = diff - HEADER_SIZE;
    X        ETAG(rbnew) = ALLOCATED;
    X        ULINK(rbnew) = rbnew;
    X        free_from_page(rbnew, seqindx);
    X        return(ptr);
    X    }
    X
    X    /* enlarging space */
    X
    X    rb=p+SIZE(p)+HEADER_SIZE; /* see if space is available from next block*/
    X    diff= -diff;
    X    if ((TAG(rb)==AVAILABLE) && ((SIZE(rb)+1)>diff))
    X    {    /* take from right block - save important info */
    X        unsigned int lsave, rsave, ssave;
    X        lsave=LLINK(rb);
    X        rsave=RLINK(rb);
    X        ssave=SIZE(rb);
    X        SIZE(p)  = size;
    X        ULINK(p) = p;
    X        ETAG(p)  = ALLOCATED;
    X        rb = p + SIZE(p) + HEADER_SIZE;
    X
    X        /* fix right block */
    X
    X        LLINK(rb) = lsave;
    X        RLINK(rb) = rsave;
    X        TAG(rb)   = AVAILABLE;
    X        SIZE(rb)  = ssave - diff;
    X        ETAG(rb)  = AVAILABLE; /* shouldn't have changed but ... */
    X        ULINK(rb) = rb;
    X
    X        /* fix neighbors on free list */
    X        LLINK(RLINK(rb)) = rb;
    X        RLINK(LLINK(rb)) = rb;
    X        return ptr;
    X    }
    X
    X    /* Finally, if room wasn't availble, allocate new block and move stuff */
    X
    X    ptrnew = malloc(size<<1);
    X    u_memcpy((int *) ptr, (int *) ptrnew, SIZE(p));
    X    free (ptr);
    X    return ptrnew;
    X
    X}
    X
    X
    Xchar *tagit(i)
    Xunsigned int i;
    X{
    X    if (i==AVAILABLE)
    X        return "AVAIL ";
    X    if (i==ALLOCATED)
    X        return "IN USE";
    X    return "*BAD* ";
    X}
    X
    X
    Xint dump_malloc()
    X{
    X    unsigned int indx, ptr, *page;
    X
    X    if (m_curindx==0)
    X    {
    X        fprintf(stderr,"\r\n No segments allocated\r\n");
    X        return(1);
    X    }
    X
    X    for (indx=1; indx<=m_curindx; indx++)
    X    {
    X        fprintf(stderr,"\r\n Segment No. %d : \r\n",indx);
    X        page=getpage(indx);
    X
    X        ptr = 0; /* first block */
    X        fprintf(stderr," Ptr      Block\r\n");
    X        fprintf(stderr," Addr     offset       LLINK  TAG    SIZE    RLINK  ETAG    UPLINK\r\n\n");
    X        while (ptr!=32768 /* last block */ )
    X        {
    X            fprintf(stderr,"%.8lx   %.5u      %.5u  %s  %.5u   %.5u  %s  %.5u \r\n",
    X              page + ptr + ALLOCATE_OFFSET,
    X              ptr, LLINK(ptr), tagit(TAG(ptr)), SIZE(ptr), RLINK(ptr),
    X                       tagit(ETAG(ptr)), ULINK(ptr));
    X
    X            ptr += HEADER_SIZE+SIZE(ptr);
    X            if (ptr<6) abort();
    X        }
    X
    X        fprintf(stderr," \r\n AV points to %u\r\n\n",AV(indx));
    X    }
    X    return(1);
    X}
    X
    X
    X/* int check_malloc()
    X{
    X    char pointers[32762];
    X    unsigned int first, cur, indx, *page;
    X
    X    for (indx=1; indx<=m_curindx; indx++);
    X    {
    X        fprintf("\nChecking segment %d for LLINKS\n", indx);
    X        for (cur==0; cur<32762; cur++)
    X            pointers[cur]=0;
    X        page=getpage(indx);
    X        first=AV(indx);
    X        cur=first;
    X        while (pointers[cur]==0)
    X        {
    X            pointers[cur]=1;
    X            cur=LLINK(cur);
    X        }
    X        if (cur != first)abort();
    X
    X        fprintf("\nChecking segment %d for RLINKS\n", indx);
    X        for (cur==0; cur<32760; cur++)
    X            pointers[cur]=0;
    X        page=getpage(indx);
    X        first=AV(indx);
    X        cur=first;
    X        while (pointers[cur]==0)
    X        {
    X            pointers[cur]=1;
    X            cur=RLINK(cur);
    X        }
    X        if (cur != first)abort();
    X    }
    X}
    X*/
SHAR_EOF
if test 12693 -ne "`wc -c < 'malloc.c'`"
then
    echo shar: "error transmitting 'malloc.c'" '(should have been 12693 characters)'
fi
fi
echo shar: "extracting 'm286.3x'" '(2318 characters)'
if test -f 'm286.3x'
then
    echo shar: "will not over-write existing file 'm286.3x'"
else
sed 's/^    X//' << \SHAR_EOF > 'm286.3x'
    X.TH M286 3X
    X.SH NAME
    Xm286 \- malloc package for iAPX286 processor
    X.SH SYNOPSIS
    X.nf
    X    char *malloc(size)
    X    unsigned size;
    X
    X    void free(ptr)
    X    char *ptr;
    X
    X    char *realloc(ptr, size)
    X    char *ptr;
    X    unsigned size;
    X
    X    char calloc(nelem, elsize)
    X    unsigned nelem, elsize;
    X
    X    int dump_malloc()
    X.fi
    X.SH DESCRIPTION
    X.I M286
    Xis a malloc(3C) compatible library designed for use on the iAPX286 processor.
    XPerformance is greatly improved over both malloc(3C) and malloc(3X) by
    Xallocating full 64K segments via the brk() system call and divving up
    Xthe segments as needed, reducing UNIX overhead. Is is found in the library
    X"m286", and is loaded if the option "-lm286" is used with cc(1) or
    Xld(1).
    X
    X.I Malloc
    Xreturns a pointer to a block of at least size bytes.
    X
    X.I Free
    Xreturns the space previously allocated with calloc() or malloc()
    Xas pointed to by the argument
    X.I ptr.
    XContents of the block are preserved until the next malloc() or calloc()
    Xcall.
    X
    X.I Realloc
    Xchanges the size of the blocked pointed to by
    X.I ptr
    Xto the size given by argument two in bytes. Contents of the block
    Xwill be unchanged up to either the original size or the new size,
    Xwhichever is smaller.
    X
    X.I Calloc
    Xallocates space via malloc and intializes the space to zeros. The
    Xamount of space allocated is set up to handle an array of
    X.I nelem
    Xelements of size
    X.I elsize.
    X
    X.I Dump_malloc
    Xprovides a means to debug pointer references by dumping a list of all
    Xblocks within
    X.I m286's
    Xfree list or those currently allocated to the standard error device. The listing
    Xcontains LLINK, RLINK which are pointers to the previous and next blocks
    Xon the free list. TAG and ETAG are flags indicating whether the block is
    Xin use or not. ULINK is always a pointer to the beginning of the block.
    XAll of the fields are displayed as indexes into a array of words within
    Xthe allocated segment.
    X
    X.SH CAVEATS
    XSince performance is gained by allocating full 64K segments, an average
    Xof 32K bytes will be wasted by the process. The maximum size block that
    Xcan be allocated is 65488 bytes. If larger sizes are needed, use brk() directly.
    X
    XThis software is copyright and can only be used and distributed for
    Xnon-commercial use. Commerical licenses can be obtained from
    [e-mail] for a very low cost.
    X.SH FILES
    X.DT
    X/usr/lib/large/libm286.a
    X.SH "SEE ALSO"
    Xmalloc(3c), malloc(3x), brk(2)
SHAR_EOF
if test 2318 -ne "`wc -c < 'm286.3x'`"
then
    echo shar: "error transmitting 'm286.3x'" '(should have been 2318 characters)'
fi
fi
echo shar: "extracting 't.c'" '(635 characters)'
if test -f 't.c'
then
    echo shar: "will not over-write existing file 't.c'"
else
sed 's/^    X//' << \SHAR_EOF > 't.c'
    X#include <stdio.h>
    X#include <malloc.h>
    X
    Xmain(argc, argv)
    Xint argc;
    Xchar *argv[];
    X{
    X    char *p;
    X    int size,i,j;
    X    if (argc!=2)
    X    {
    X        printf("%s: Usage - t number \n",argv[0]);
    X        printf(" Where 'number' is the number of kilobytes to allocate\n");
    X        exit(1);
    X    }
    X
    X    if ((size=atoi(argv[1])) == 0)
    X    {
    X        printf("%s: Bad argument, must be integer in kilobytes",argv[0]);
    X        exit(1);
    X    }
    X
    X    for (i=0; i<size; i++)
    X        for (j=0; j<10; j++)
    X            if ((p=malloc(100))==NULL)
    X            {
    X                printf("\nNot enough memory available\n");
    X                printf("Was only able to allocate %ld bytes",i*1024L+j*100L);
    X                exit(2);
    X            } else putchar('.');
    X    putchar('\n');
    X    return 0;
    X}
SHAR_EOF
if test 635 -ne "`wc -c < 't.c'`"
then
    echo shar: "error transmitting 't.c'" '(should have been 635 characters)'
fi
fi
echo shar: "extracting 'tcheck.c'" '(1564 characters)'
if test -f 'tcheck.c'
then
    echo shar: "will not over-write existing file 'tcheck.c'"
else
sed 's/^    X//' << \SHAR_EOF > 'tcheck.c'
    X#include <stdio.h>
    X#include <malloc.h>
    X#include <signal.h>
    Xchar *calloc();
    X
    X#define NSEGS 512   /* must be power of two  - this program allocates
    X            up to NSEGS * 1K bytes            */
    X
    Xchar *p[NSEGS];
    X
    X#ifdef DEBUG
    Xvoid fault(no)
    Xint no;
    X{
    X    fprintf(stderr,"Caught signal number %d\n",no);
    X    dump_malloc();
    X    abort();
    X}
    X#endif
    X
    X
    Xvoid print_pointers()
    X{
    X    int i;
    X    fprintf(stderr,"\n Pointers are : ");
    X    for (i=0; i<NSEGS; i++)
    X        fputc( (p[i]==NULL ? 'F':'T'), stderr);
    X    fputc('\n',stderr);
    X}
    X
    X
    X
    Xmain(argc, argv)
    Xint argc;
    Xchar *argv[];
    X{
    X    int j,k;
    X    unsigned s,fill;
    X    long i;
    X
    X#ifdef DEBUG
    X    signal(SIGINT,fault);
    X#endif
    X
    X    for (i=0; i<NSEGS; i++)
    X        p[i]=NULL;
    X
    X    for (i=0; i<100000; i++)
    X    {
    X        k= rand() & (NSEGS - 1); /* choose a pointer */
    X        if (p[k] == NULL)
    X        {
    X            int call_type;
    X/*            print_pointers(); */
    X            s=(unsigned) rand() & 0x3ff;  /* pick a size */
    X            fprintf(stderr," %ld : Allocating a size of %u to pointer %d ",i,s,k);
    X
    X            call_type = rand() & 1;
    X            p[k] = ( call_type ? malloc(s) : calloc(s,1) );
    X            fprintf(stderr,"and getting %lx using %s\n",
    X                p[k], ( call_type ? "malloc" : "calloc"));
    X            for (fill=0; fill<s; fill++)  /* fill the buffer */
    X                p[k] [fill] = (char) (i & 0xff);
    X
    X        }
    X        j=rand() & (NSEGS-1);   /* choose another pointer */
    X        if (p[j] != NULL)
    X        {
    X            fprintf(stderr," %ld : freeing %lx from pointer %d\n",i,p[j],j);
    X            free(p[j]);
    X            p[j]=NULL;
    X        }
    X
    X        j=rand() & (NSEGS-1);
    X        if (p[j] != NULL)
    X        {
    X            s=rand()&0x3ff;
    X            fprintf(stderr," %ld : realloc %lx to size %d on pointer %d\n",
    X                i, p[j], s,j);
    X            p[j]=realloc(p[j], s);
    X        }
    X
    X    }
    X}
SHAR_EOF
if test 1564 -ne "`wc -c < 'tcheck.c'`"
then
    echo shar: "error transmitting 'tcheck.c'" '(should have been 1564 characters)'
fi
fi
exit 0
#    End of shell archive